package basic.courseLearn07.problem;

import basic.courseLearn07.Edge;
import basic.courseLearn07.Graph;
import basic.courseLearn07.MyUnionFindSet;
import basic.courseLearn07.Node;
import org.junit.Test;

import java.util.*;

//kruskal算法，最小生成树问题
public class KruskalAlgorithm {

    class MinCompare implements Comparator<Edge> {

        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight-o2.weight;
        }
    }


    //kruskal算法
    public void kruskal(Graph graph){
        //1. 定义小根堆，根据边的权重
        PriorityQueue<Edge> minHeap = new PriorityQueue<>(new MinCompare());
        for(Edge edge:graph.edges){
            minHeap.add(edge);
        }

        //2. 定义size，避免森林情况；初始化并查集
        int size = 0;
        MyUnionFindSet unionFindSet = new MyUnionFindSet();
        List<Node> list =  new ArrayList<Node>();
        list.addAll(graph.nodes.values());
        unionFindSet.init(list);

        //3. 进入循环
        while(size+1<graph.nodes.size()){
            //3.1 取出权重最小的边
            Edge edge = minHeap.poll();
            //3.2 判断是否形成环
            if(!unionFindSet.isSameSet(edge.from,edge.to)){
                unionFindSet.union(edge.from,edge.to);
                System.out.println(edge.from.value + "->" + edge.to.value + "(" + edge.weight + ")");
                size++;
            }
        }
    }

    @Test
    public void test(){
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        HashMap<Integer, Node> map = new HashMap<>();
        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        graph.setNodes(map);

        Edge edge1 = new Edge(2, node1, node2);
        Edge edge2 = new Edge(1, node1, node4);
        Edge edge3  = new Edge(3, node1, node5);

        Edge edge4 = new Edge(2, node2, node1);
        Edge edge5 = new Edge(4, node2, node4);
        Edge edge6 = new Edge(4, node2, node5);
        Edge edge7 = new Edge(5, node2, node3);

        Edge edge8 = new Edge(5, node3, node2);
        Edge edge9 = new Edge(7, node3, node5);

        Edge edge10= new Edge(1, node4, node1);
        Edge edge11= new Edge(4, node4, node2);
        Edge edge12 = new Edge(3, node4, node5);

        Edge edge13 = new Edge(3, node5, node4);
        Edge edge14 = new Edge(3, node5, node1);
        Edge edge15 = new Edge(4, node5, node2);
        Edge edge16 = new Edge(7, node5, node3);

        HashSet<Edge> edges = new HashSet<>();
        edges.add(edge1);
        edges.add(edge2);
        edges.add(edge3);
        edges.add(edge4);
        edges.add(edge5);
        edges.add(edge6);
        edges.add(edge7);
        edges.add(edge8);
        edges.add(edge9);
        edges.add(edge10);
        edges.add(edge11);
        edges.add(edge12);
        edges.add(edge13);
        edges.add(edge14);
        edges.add(edge15);
        edges.add(edge16);
        graph.setEdges(edges);

        kruskal(graph);




    }



}
